package class33;

import java.util.HashMap;

/**
 * @author zhangchaoliang
 * create 2022
 *
 * 给定一个整型数组arr，其中可能有正有负有零。
 * 你可以随意把整个数组切成若干个不相容的子数组，
 * 求异或和为0的子数组最多可能有多少个？
 * 整数异或和定义：把数组中所有的数异或起来得到的值。
 */
public class MostEOR {

    public static int mostEOR(int[] arr) {
        int N = arr.length;
        //dp[i] -> arr[0...i]  在最优划分的情况下，异或和为0最多的部分是多少个？
        int[] dp = new int[N];
        //key : 某个前缀异或和
        //value: 这个前缀异或和出现的最晚的结尾位置（0~value）
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {//i所在的最后一块
            sum ^= arr[i];//sum  -> [0..i]所有数的异或和
            //假设sum上次出现的结尾是K，0~k的异或和是sum，0~i的异或和也是sum,k+1~i是异或和等于0的
            //前缀异或和出现的最晚的结尾位置，k+1是离i最近的
            if (map.containsKey(sum)) {//上一次，这个异或和出现的位置
                //pre -> pre + 1 -> i ， 最有划分，最后一个部分的开始位置
                //(pre +1 ,i)最后的部分
                int pre = map.get(sum);
                dp[i] = pre == -1 ? 1 : (dp[pre] + 1);
            }
            if (i > 0) {
                dp[i] = Math.max(dp[i - 1], dp[i]);
            }
            map.put(sum, i);
        }
        return dp[dp.length - 1];
    }
}
